package leetcode.Hot100;

import leetcode.TreeNode;

/**
 * @author Cheng Jun
 * Description: 给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
 * <p>
 * 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，
 * 否则不为 NULL 的节点将直接作为新二叉树的节点。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/merge-two-binary-trees
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2021/12/3 14:15
 * 编程感悟：
 * 分析题意 找思路，写伪代码，大脑编译运行，优化伪代码，敲代码，debugger运行，提交。
 * 成功（看看时间复杂度、空间复杂度有没有优化点）。错误，验证思路，思路错误，重新找思路，思路没错，fix bug。
 * <p>
 * 解题过程中，不要一烦就删代码，想着重新写。
 */
public class mergeTrees {

    public static void main(String[] args) {
        TreeNode a = new TreeNode(3);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(1, b, a);
        TreeNode b1 = new TreeNode(2);
        TreeNode c1 = new TreeNode(1, b1, null);
        System.out.println(mergeTrees(c, c1));
    }

    // 实现：合并两个节点，产生一个新节点，并维护新节点的左右子节点
    static TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) {
            return null;
        }
        if (root1 != null && root2 == null) {
            return root1;
        }
        if (root1 == null && root2 != null) {
            return root2;
        }
        // 合并当前两个节点，产生一个新节点，维护左右子节点
        TreeNode node = new TreeNode(root1.val + root2.val);
        node.left = mergeTrees(root1.left, root2.left);
        node.right = mergeTrees(root1.right, root2.right);
        return node;
    }

    // 错误编程示例，不分析，以为简单 上来就写。
    static void merge(TreeNode node1, TreeNode node2, TreeNode dummy) {
        if (node1 == null && node2 == null) {
            return;
        } else if (node1 != null && node2 == null) {

        } else if (node1 != null && node2 == null) {

        } else {
            dummy = new TreeNode(node1.val + node2.val);
            merge(node1.left, node2.left, null);
        }
        // node1.left node2.left
        // node1.right node2.right
    }
}
